package cn.itedus.lottery.domain.strategy.service.algorithm.impl;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/9/8 12:31
 */
public class 蓄水池算法 {

    /*
     这个就更加的抽象了

     就定义 n 个令牌 (令牌的数量不增加)
     那道就去执行后续的流程, 拿不到直接返回!

     - 这种适用于 瞬时秒杀!
     比如 xxx直播间  十台 iphone 100元抢, 这种, 直接
     而且需要多层过滤, 每一层都过滤到一些流量
     */

    // 实现的等概率
    public static class RandomBox {
        private int[] bag; // 池子
        private int N; // 池子的大小
        private int count; // 表示 当前  球的编号 (从 1 开始, 0 不算 )

        public RandomBox(int capacity) {
            bag = new int[capacity];
            N = capacity;
            count = 0;
        }

        private int rand(int max) {
            return (int) (Math.random() * max) + 1;
        }

        public void add(int num) {
            count++;
            if (count <= N) {
                bag[count - 1] = num; // 如果池子还没满, 直接 入池子
            } else {
                if (rand(count) <= N) { // 如果池子 满了, 以 N / count  的概率决定是否入池
                    bag[rand(N) - 1] = num;
                }
            }
        }

        public int[] choices() {
            int[] ans = new int[N];
            for (int i = 0; i < N; i++) {
                ans[i] = bag[i];
            }
            return ans;
        }

    }

    // 测试代码
    public static void main(String[] args) {
        System.out.println("hello");
        int all = 100;
        int choose = 10;
        int testTimes = 50000;
        int[] counts = new int[all + 1];
        for (int i = 0; i < testTimes; i++) {
            RandomBox box = new RandomBox(choose);
            for (int num = 1; num <= all; num++) {
                box.add(num);
            }
            int[] ans = box.choices();
            for (int j = 0; j < ans.length; j++) {
                counts[ans[j]]++;
            }
        }

        for (int i = 0; i < counts.length; i++) {
            System.out.println(i + " times : " + counts[i]);
        }

    }

}
